1. Field of the Invention
The present invention relates in general to a method and system for multicasting communications using routing schemes in which multiple independent trees or paths are employed to minimize communications interruptions due to tree or path failures. The invention is particularly suited for use in ad hoc networks.
2. Description of the Background Art
An ad hoc network consists of a collection of mobile routers that are interconnected via wireless links and are free to move about arbitrarily. This technology has its roots in DARPA packet radio networks. Research on multi hop packet-switching radio networks started in the 1970s, with its initial motivation in military applications. Their attractiveness was (and continues to be) because of the ease and speed of deployment in hard-to-access environments. In recent years, interest in ad hoc networks has grown with improvements in laptop computers including greater computational power, longer battery life and decreased weight. Advent of ubiquitous computing and the proliferation of portable computing devices have further increased the importance of efficient routing in mobile networks.
One of the most pressing needs for enhanced communication protocols come from multi point applications, which involve the one-to-many communication model (i.e., multicasting operation). Such applications cover a very wide spectrum including software distribution, replicated database update, command and control systems, audio/video conferencing, and distributed interactive simulation.
Multicasting is an efficient communication tool for use in multi point applications. Many of the proposed multicast routing protocols, both for the Internet and for ad hoc networks, construct trees over which information is transmitted. Using trees is evidently more efficient than the brute force approach of sending the same information from the source individually to each of the receivers. Another benefit of using trees is that routing decisions at the intermediate nodes become very simple: a router in a multicast tree that receives a multicast packet over an in-tree interface forwards the packet over the rest of its in-tree interfaces.
Multicast routing algorithms in the Internet can be classified into three broad categories: Shortest Path Tree algorithms, Minimum Cost Tree algorithms, and Constrained Tree algorithms. There are two fundamental approaches in designing multicast routing—one is to minimize the distance (or cost) from the sender to each receiver individually (shortest path tree algorithms) and the other is to minimize the overall (total) cost of the multicast tree. Practical considerations lead to a third category of algorithms which try to optimize both constraints using some metric (minimum cost trees with constrained delays). The majority of multicast routing protocols in the Internet are based on shortest path trees, because of their ease of implementation. Also, they provide minimum delay from sender to receiver, which is desirable for many real-life multicast applications. However shared trees are used in some more recent protocols (like PIM and CBT) in order to minimize states stored in the routers.
Multicasting in ad hoc networks is more challenging than in the Internet, because of the need to optimize the use of several resources simultaneously. Firstly, nodes in ad hoc networks are battery-power limited. Furthermore, data travels over the air and wireless resources are scarce. Secondly, there is no centralized access point or existing infrastructure (like in the cellular network) to keep track of the node mobility. Thirdly, the status of communication links between routers is a function of their positions, transmission power levels, etc. The mobility of routers and randomness of other connectivity factors lead to a network with a potentially unpredictable and rapidly changing topology. This means that by the time a reasonable amount of information about the topology of the network is collected and a tree is computed, there may be very little time before this computed tree becomes useless.
Work on multicast routing in ad hoc networks gained momentum in the mid 1990s. Some early approaches to provide multicast support in ad hoc networks, such as for example, Shared Tree Wireless Network Multicast, consisted of adapting the existing Internet multicasting protocols. Other protocols, such as On-Demand Multicast Routing Protocol (ODMRP) have been designed specifically for ad hoc networks. ODMRP is a mesh based, on-demand protocol that uses a soft state approach for maintenance of the message transmission structure. It exploits robustness of mesh structure to frequent route failure and gains stability at the expense of bandwidth. The Core Assisted Mesh Protocol (CAMP) attempts to remedy this excessive overhead, while still using a mesh by using a core for route discovery. AMRIS is a protocol that constructs a shared delivery tree rooted at a node, with ID-numbers increasing as they radiate from the source. Local route recovery is made possible due to this property of ID numbers, hence reducing the route recovery time and also confining route recovery traffic to the region of link failures.
One common characteristic of most of these approaches is that they react to a link failure, i.e. they act after a link has already failed, causing a significant delay in route recovery. As a result, communications between selected nodes in the network can be disabled for a significant period of time. A need therefore exists for a multicasting routing protocol that can minimize the time period between failure of a link and route recovery.